{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sort the Matrix Diagonally"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: diagonalSort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将矩阵按对角线排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>矩阵对角线</strong> 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 <code>mat</code> 有 <code>6</code> 行 <code>3</code> 列，从 <code>mat[2][0]</code> 开始的 <strong>矩阵对角线</strong> 将会经过 <code>mat[2][0]</code>、<code>mat[3][1]</code> 和 <code>mat[4][2]</code> 。</p>\n",
    "\n",
    "<p>给你一个 <code>m * n</code> 的整数矩阵 <code>mat</code> ，请你将同一条 <strong>矩阵对角线 </strong>上的元素按升序排序后，返回排好序的矩阵。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/25/1482_example_1_2.png\" style=\"height: 198px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]\n",
    "<strong>输出：</strong>[[1,1,1,1],[1,2,2,2],[1,2,3,3]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]\n",
    "<strong>输出：</strong>[[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat.length</code></li>\n",
    "\t<li><code>n == mat[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 100</code></li>\n",
    "\t<li><code>1 <= mat[i][j] <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sort-the-matrix-diagonally](https://leetcode.cn/problems/sort-the-matrix-diagonally/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sort-the-matrix-diagonally](https://leetcode.cn/problems/sort-the-matrix-diagonally/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[3,3,1,1],[2,2,1,2],[1,1,1,2]]', '[[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        def help(x, y):\n",
    "            pos = []\n",
    "            data = []\n",
    "            while x < m and y < n:\n",
    "                pos.append((x, y))\n",
    "                data.append(mat[x][y])\n",
    "                x += 1\n",
    "                y += 1\n",
    "\n",
    "            data.sort()\n",
    "            for i, p in enumerate(pos):\n",
    "                mat[p[0]][p[1]] = data[i]\n",
    "\n",
    "        for i in range(m):\n",
    "            help(i, 0)\n",
    "        \n",
    "        for j in range(1, n):\n",
    "            help(0, j)\n",
    "        \n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        # 除了第一条和最后一条线，一共只有m + n - 3条线\n",
    "        for t in range(1, m + n - 2):\n",
    "            row_start = row = max(n - 1 - t, 0)\n",
    "            col_start = col = max(t - n + 1, 0)\n",
    "            l = []\n",
    "            while row < n and col < m:\n",
    "                # 利用堆排序\n",
    "                heappush(l, mat[row][col])\n",
    "                row += 1\n",
    "                col += 1\n",
    "\n",
    "            row = row_start\n",
    "            col = col_start\n",
    "            while row < n and col < m:\n",
    "                mat[row][col] = heappop(l)\n",
    "                row += 1\n",
    "                col += 1\n",
    "\n",
    "        return mat\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        for j in range(n):\n",
    "            cur=[]\n",
    "            for x in range(min(m,n-j)):\n",
    "                cur.append(mat[x][x+j])\n",
    "            # print(cur)\n",
    "            cur.sort(reverse=True)\n",
    "            for x in range(min(m,n-j)):\n",
    "                mat[x][x+j]=cur.pop()\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            cur=[]\n",
    "            for x in range(min(m-i,n)):\n",
    "                cur.append(mat[x+i][x])\n",
    "            # print(cur)\n",
    "            cur.sort(reverse=True)\n",
    "            for x in range(min(m-i,n)):\n",
    "                mat[x+i][x]=cur.pop()\n",
    "\n",
    "        \n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def my_sort(self, mat, list_sort, list_loc):\n",
    "        list_sort.sort()\n",
    "        list_len = len(list_sort)\n",
    "        k = 0\n",
    "        while k < list_len:\n",
    "            han = list_loc[k][0]\n",
    "            lie = list_loc[k][1]\n",
    "            mat[han][lie] = list_sort[k]\n",
    "            k += 1\n",
    "\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        mat_hang = len(mat)\n",
    "        mat_lie = len(mat[0])\n",
    "        up_flag = 0\n",
    "        while up_flag < mat_lie:\n",
    "            han = 0\n",
    "            lie = up_flag\n",
    "            list_sort = []\n",
    "            list_loc = []\n",
    "            while han < mat_hang and lie < mat_lie:\n",
    "                list_sort.append(mat[han][lie])\n",
    "                list_loc.append([han, lie])\n",
    "                han += 1\n",
    "                lie += 1\n",
    "                if han == mat_hang or lie == mat_lie:\n",
    "                    self.my_sort(mat, list_sort, list_loc)\n",
    "            up_flag += 1\n",
    "        # 去对角线上半部分\n",
    "        low_flag = 1\n",
    "        while low_flag < mat_hang:\n",
    "            lie = 0\n",
    "            han = low_flag\n",
    "            list_sort = []\n",
    "            list_loc = []\n",
    "            while lie < mat_lie and han < mat_hang:\n",
    "                list_sort.append(mat[han][lie])\n",
    "                list_loc.append([han, lie])\n",
    "                han += 1\n",
    "                lie += 1\n",
    "                if han == mat_hang or lie == mat_lie:\n",
    "                    self.my_sort(mat, list_sort, list_loc)\n",
    "            low_flag += 1\n",
    "\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        for k in range(min(m,n)):\n",
    "            for i in range(m-2,k-1,-1):\n",
    "                for j in range(n-2,k-1,-1):\n",
    "                    if mat[i][j] > mat[i+1][j+1]:\n",
    "                        mat[i][j],mat[i+1][j+1] = mat[i+1][j+1],mat[i][j]\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[0 for _ in mat[0]] for _ in mat]\n",
    "        isValid = lambda x, y: x > -1 and x < len(mat) and y > -1 and y < len(mat[0])\n",
    "        start = [(i, 0) for i in range(len(mat))] + [(0, i) for i in range(len(mat[0]))]\n",
    "\n",
    "        for x, y in start:\n",
    "            bakX, bakY = x, y\n",
    "            tmp = []\n",
    "\n",
    "            while isValid(x, y):\n",
    "                tmp.append(mat[x][y])\n",
    "                x, y = x + 1, y + 1\n",
    "\n",
    "            x, y = bakX, bakY\n",
    "            for j in sorted(tmp):\n",
    "                ans[x][y] = j\n",
    "                x, y = x + 1, y + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        i, j = 0, 0\n",
    "        while j < n:\n",
    "            nums = []\n",
    "            x, y = i, j\n",
    "            while x < m and y < n:\n",
    "                nums.append(mat[x][y])\n",
    "                x += 1\n",
    "                y += 1\n",
    "            nums.sort()\n",
    "            x, y = i, j\n",
    "            k = 0\n",
    "            while x < m and y < n:\n",
    "                mat[x][y] = nums[k]\n",
    "                x += 1\n",
    "                y += 1\n",
    "                k += 1\n",
    "            j += 1\n",
    "        \n",
    "        i, j = 1, 0\n",
    "        while i < m:\n",
    "            nums = []\n",
    "            x, y = i, j\n",
    "            while x < m and y < n:\n",
    "                nums.append(mat[x][y])\n",
    "                x += 1\n",
    "                y += 1\n",
    "            nums.sort()\n",
    "            x, y = i, j\n",
    "            k = 0\n",
    "            while x < m and y < n:\n",
    "                mat[x][y] = nums[k]\n",
    "                x += 1\n",
    "                y += 1\n",
    "                k += 1\n",
    "            i += 1\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        def help(x, y):\n",
    "            pos = []\n",
    "            data = []\n",
    "            while x < m and y < n:\n",
    "                pos.append((x, y))\n",
    "                data.append(mat[x][y])\n",
    "                x += 1\n",
    "                y += 1\n",
    "\n",
    "            data.sort()\n",
    "            ptr = 0\n",
    "            for x, y in pos:\n",
    "                mat[x][y] = data[ptr]\n",
    "                ptr += 1\n",
    "\n",
    "        for i in range(m):\n",
    "            help(i, 0)\n",
    "        \n",
    "        for j in range(1, n):\n",
    "            help(0, j)\n",
    "        \n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        start_point = [(0,0)] + [(i, 0) for i in range(1, m)] + [(0, j) for j in range(1, n)]\n",
    "        for tup in start_point:\n",
    "            i, j = tup\n",
    "            res = [mat[i+dx][j+dx] for dx in range(min(m, n)) if i + dx < m and j + dx < n]\n",
    "            res.sort()\n",
    "\n",
    "            for k in range(len(res)):\n",
    "                mat[i+k][j+k] = res[k] \n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/problems/sort-the-matrix-diagonally/description/\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        rows, cols = mat.__len__(), mat[0].__len__()\n",
    "        size = min(rows, cols)\n",
    "        # 从[0, 0]对角线开始，向上处理，向下处理，遇到下标不符合预期，直接过滤掉，不参与排序处理\n",
    "        main_row_indexes = []\n",
    "        for i in range(size):\n",
    "            main_row_indexes.append([i, i])\n",
    "\n",
    "        def sort_row(mat, row_indexes):\n",
    "            row = []\n",
    "            for index in row_indexes:\n",
    "                row.append(mat[index[0]][index[1]])\n",
    "            row.sort()\n",
    "            for i, index in enumerate(row_indexes):\n",
    "                mat[index[0]][index[1]] = row[i]\n",
    "        sort_row(mat, main_row_indexes)\n",
    "        # print(\"mian_row_indexes=\", main_row_indexes)\n",
    "\n",
    "        # 往上是 cols-1轮\n",
    "        for i in range(1, cols):\n",
    "            indexes = []\n",
    "            for idx in main_row_indexes:\n",
    "                if idx[1] + i >= cols:\n",
    "                    continue\n",
    "                indexes.append([idx[0], idx[1]+i])\n",
    "            # print(\"upper indexes=\", indexes)\n",
    "            sort_row(mat, indexes)\n",
    "\n",
    "        for i in range(1, rows):\n",
    "            indexes = []\n",
    "            for idx in main_row_indexes:\n",
    "                if idx[0] + i >= rows:\n",
    "                    continue\n",
    "                indexes.append([idx[0]+i, idx[1]])\n",
    "            # print(\"downer indexes=\", indexes)\n",
    "            sort_row(mat, indexes)\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        # 除了第一条和最后一条线，一共只有m + n - 3条线\n",
    "        for t in range(1, m + n - 2):\n",
    "            l = []\n",
    "            # 使用堆排序\n",
    "            row = max(n - t - 1, 0)\n",
    "            col = max(t - n + 1, 0)\n",
    "            while row < n and col < m:\n",
    "                heappush(l, mat[row][col])\n",
    "                row += 1\n",
    "                col += 1\n",
    "            # 改变原矩阵\n",
    "            row = max(n - t - 1, 0)\n",
    "            col = max(t - n + 1, 0)\n",
    "            while row < n and col < m:\n",
    "                mat[row][col] = heappop(l)\n",
    "                row += 1\n",
    "                col += 1\n",
    "                \n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        row, col = len(mat), len(mat[0])\n",
    "\n",
    "        start_point = [(0,0)]+[(i,0) for i in range(1,row)]+[(0,j) for j in range(1,col)]\n",
    "        for tup in start_point:\n",
    "            i, j = tup\n",
    "            res = [mat[i+n][j+n] for n in range(0, min(row,col)) if i+n <row and j+n<col]\n",
    "            res.sort()\n",
    "            for k in range(len(res)):\n",
    "                mat[i+k][j+k] = res[k]    \n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        temp = []\n",
    "        for i in range(m):\n",
    "            temp = []\n",
    "            l = min(m, n)\n",
    "            for j in range(l):\n",
    "                if i+j < m and j < n:\n",
    "                    temp.append(mat[i+j][j])\n",
    "            temp.sort()\n",
    "            for j in range(l):\n",
    "                if i+j < m and j < n:\n",
    "                    mat[i+j][j] = temp[j]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            temp = []\n",
    "            l = min(m, n)\n",
    "            for j in range(l):\n",
    "                if j < m and i+j < n:\n",
    "                    temp.append(mat[j][i+j])\n",
    "            temp.sort()\n",
    "            for j in range(l):\n",
    "                if j < m and i+j < n:\n",
    "                    mat[j][i+j] = temp[j]\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        row = len(mat)\n",
    "        col = len(mat[0])\n",
    "        i = len(mat)-1\n",
    "        j = 0\n",
    "        while i>0:\n",
    "            tmp_i = i\n",
    "            tmp_j = j\n",
    "            tmp_list = list()\n",
    "            while tmp_i<row and tmp_j<col:\n",
    "                tmp_list.append(mat[tmp_i][tmp_j])\n",
    "                tmp_i = tmp_i+1\n",
    "                tmp_j = tmp_j+1\n",
    "            tmp_list.sort(reverse=True)\n",
    "            tmp_i = i\n",
    "            tmp_j = j\n",
    "            while tmp_i<row and tmp_j<col:\n",
    "                mat[tmp_i][tmp_j] = tmp_list[-1]\n",
    "                tmp_list.pop()\n",
    "                tmp_i = tmp_i+1\n",
    "                tmp_j = tmp_j+1\n",
    "            i -= 1 \n",
    "        while j<col:\n",
    "            tmp_i = i\n",
    "            tmp_j = j\n",
    "            tmp_list = list()\n",
    "            while tmp_i<row and tmp_j<col:\n",
    "                tmp_list.append(mat[tmp_i][tmp_j])\n",
    "                tmp_i = tmp_i+1\n",
    "                tmp_j = tmp_j+1                \n",
    "            tmp_list.sort(reverse=True)\n",
    "            tmp_i = i\n",
    "            tmp_j = j\n",
    "            while tmp_i<row and tmp_j<col:\n",
    "                mat[tmp_i][tmp_j] = tmp_list[-1]\n",
    "                tmp_list.pop()\n",
    "                tmp_i = tmp_i+1\n",
    "                tmp_j = tmp_j+1                \n",
    "            j += 1\n",
    "\n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        # 作用：处理任意一条对角线\n",
    "        # 输入：对角线的起始坐标\n",
    "        # 输出：无，将mat的该条对角线排好序\n",
    "        def help(x, y):\n",
    "            pos = []\n",
    "            data = []\n",
    "\n",
    "            while x < m and y < n:\n",
    "                pos.append((x, y))\n",
    "                data.append(mat[x][y])\n",
    "                x += 1\n",
    "                y += 1\n",
    "            #end\n",
    "\n",
    "            data.sort()\n",
    "            for i, p in enumerate(pos):\n",
    "                mat[p[0]][p[1]] = data[i]\n",
    "            #end\n",
    "        #end\n",
    "\n",
    "        for i in range(m): help(i, 0)\n",
    "        \n",
    "        for j in range(1, n): help(0, j)\n",
    "        \n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        row = len(mat)\n",
    "        col = len(mat[0])\n",
    "        \n",
    "        # 对角线排序函数\n",
    "        def sortDiagonal(start_i, start_j):\n",
    "            diag = []\n",
    "            i, j = start_i, start_j\n",
    "            \n",
    "            # 提取对角线元素\n",
    "            while i < row and j < col:\n",
    "                diag.append(mat[i][j])\n",
    "                i += 1\n",
    "                j += 1\n",
    "            \n",
    "            # 对对角线元素进行排序\n",
    "            diag.sort()\n",
    "            \n",
    "            # 将排序后的元素重新赋值给对角线位置\n",
    "            i, j = start_i, start_j\n",
    "            for num in diag:\n",
    "                mat[i][j] = num\n",
    "                i += 1\n",
    "                j += 1\n",
    "        \n",
    "        # 对左上角对角线进行排序\n",
    "        for i in range(row):\n",
    "            sortDiagonal(i, 0)\n",
    "        \n",
    "        # 对左下角对角线进行排序\n",
    "        for j in range(1, col):\n",
    "            sortDiagonal(0, j)\n",
    "        \n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        for i in range(len(mat)):\n",
    "            t=[]\n",
    "            x,y=i,0\n",
    "            while (0<=x<len(mat) and 0<=y<len(mat[0])):\n",
    "                t.append(mat[x][y])\n",
    "                x+=1\n",
    "                y+=1\n",
    "            t.sort()\n",
    "            x,y=i,0\n",
    "            index=0\n",
    "            while (0<=x<len(mat) and 0<=y<len(mat[0])):\n",
    "                mat[x][y]=t[index]\n",
    "                x+=1\n",
    "                y+=1\n",
    "                index+=1\n",
    "        for j in range(len(mat[0])):\n",
    "            t=[]\n",
    "            x,y=0,j\n",
    "            while (0<=x<len(mat) and 0<=y<len(mat[0])):\n",
    "                t.append(mat[x][y])\n",
    "                x+=1\n",
    "                y+=1\n",
    "            t.sort()\n",
    "            x,y=0,j\n",
    "            index=0\n",
    "            while (0<=x<len(mat) and 0<=y<len(mat[0])):\n",
    "                mat[x][y]=t[index]\n",
    "                x+=1\n",
    "                y+=1\n",
    "                index+=1\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n, st = len(mat), len(mat[0]), {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i - j in st:\n",
    "                    st[i - j].append(mat[i][j])\n",
    "                else:\n",
    "                    st[i - j] = [mat[i][j]]\n",
    "        for key, val in st.items():\n",
    "            val.sort()\n",
    "            val.append(0)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mat[i][j] = st[i - j][st[i - j][-1]]\n",
    "                st[i - j][-1] += 1\n",
    "        return mat\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        t=min(m,n)\n",
    "        ans=[[0]*n for _ in range(m)]\n",
    "        for i in range(1-m,n):\n",
    "            lst=[]\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    if k-j==i:\n",
    "                        lst.append(mat[j][k])\n",
    "            lst.sort()\n",
    "            p=len(lst)\n",
    "            if i>=0:\n",
    "                for u in range(p):\n",
    "                    ans[u][u+i]=lst[u]\n",
    "            else:\n",
    "                for u in range(p):\n",
    "                    ans[u-i][u]=lst[u]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        row, col = len(mat), len(mat[0])\n",
    "\n",
    "        start_point = [(0,0),]+[(i,0) for i in range(1,row)]+[(0,j) for j in range(1,col)]\n",
    "        for tup in start_point:\n",
    "            i,j = tup\n",
    "            res = [mat[i+n][j+n] for n in range(0,min(row,col)) if i+n <row and j+n<col]\n",
    "            res.sort()\n",
    "\n",
    "            for k in range(len(res)):\n",
    "                mat[i+k][j+k] = res[k]\n",
    "        \n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        y=len(mat)-1\n",
    "        x=0\n",
    "        while 0<=y and x<len(mat[0]):\n",
    "            stack=queue.deque()\n",
    "            s_y=y\n",
    "            s_x=x\n",
    "            while 0<=s_y<len(mat) and 0<=s_x<len(mat[0]):\n",
    "                stack.append(mat[s_y][s_x])\n",
    "                s_y+=1\n",
    "                s_x+=1\n",
    "            stack=queue.deque(sorted(stack))\n",
    "\n",
    "            s_y=y\n",
    "            s_x=x\n",
    "            while 0 <= s_y < len(mat) and 0 <= s_x < len(mat[0]):\n",
    "                mat[s_y][s_x]=stack.popleft()\n",
    "                s_y+=1\n",
    "                s_x+=1\n",
    "            if y:\n",
    "                y-=1\n",
    "            else:\n",
    "                x+=1\n",
    "        return mat\n",
    "\n",
    "# leetcode submit region end(Prohibit modification and deletion)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        maps = defaultdict(list)\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                maps[i-j].append(mat[i][j])\n",
    "        for k, v in maps.items():\n",
    "            v.sort()\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res[i][j] = maps[i-j].pop(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "      m, n = len(mat), len(mat[0])\n",
    "      for i in range(m):\n",
    "        x, y = i, 0\n",
    "        nums = []\n",
    "        while x < m and y < n:\n",
    "          nums.append(mat[x][y])\n",
    "          x += 1\n",
    "          y += 1\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        x, y = i, 0\n",
    "        while x < m and y < n:\n",
    "          mat[x][y] = nums.pop()\n",
    "          x += 1\n",
    "          y += 1\n",
    "\n",
    "      for j in range(1, n):\n",
    "        x, y = 0, j\n",
    "        nums = []\n",
    "        while x < m and y < n:\n",
    "          nums.append(mat[x][y])\n",
    "          x += 1\n",
    "          y += 1\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        x, y = 0, j\n",
    "        while x < m and y < n:\n",
    "          mat[x][y] = nums.pop()\n",
    "          x += 1\n",
    "          y += 1\n",
    "\n",
    "      return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        # 除了第一条和最后一条线，一共只有m + n - 3条线\n",
    "        for t in range(1, m + n - 2):\n",
    "            row = max(n - 1 - t, 0)\n",
    "            col = max(t - n + 1, 0)\n",
    "            l = []\n",
    "            while row < n and col < m:\n",
    "                # 利用堆排序\n",
    "                heappush(l, mat[row][col])\n",
    "                row += 1\n",
    "                col += 1\n",
    "\n",
    "            row = max(n - 1 - t, 0)\n",
    "            col = max(t - n + 1, 0)\n",
    "            while row < n and col < m:\n",
    "                mat[row][col] = heappop(l)\n",
    "                row += 1\n",
    "                col += 1\n",
    "                \n",
    "        return mat\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        rows = len(mat)\n",
    "        cols = len(mat[0])\n",
    "        a = []\n",
    "        for row in range(rows):\n",
    "            a.append([row, 0])\n",
    "        for col in range(1, cols):\n",
    "            a.append([0, col])\n",
    "        #print(a)\n",
    "        \n",
    "        for t in a:\n",
    "            b = []\n",
    "            c = []\n",
    "            i = 0\n",
    "            while t[0] + i < rows and t[1] + i < cols:\n",
    "                b.append([t[0]+i, t[1]+i])\n",
    "                c.append(mat[t[0]+i][t[1]+i])\n",
    "                i += 1\n",
    "            c = sorted(c)\n",
    "            for j in range(len(c)):\n",
    "                mat[b[j][0]][b[j][1]] = c[j]\n",
    "            #print(mat)\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        row, col = len(mat), len(mat[0])\n",
    "        for j in range(col):\n",
    "            tmp_row = 0\n",
    "            store_tmp = []\n",
    "            while 0 <= j + tmp_row < col and 0 <= tmp_row < row:\n",
    "                store_tmp.append(mat[tmp_row][tmp_row + j])\n",
    "                tmp_row += 1\n",
    "            store_tmp = sorted(store_tmp)\n",
    "            ind, tmp_row = 0, 0\n",
    "            while 0 <= j + tmp_row < col and 0 <= tmp_row < row:\n",
    "                mat[tmp_row][tmp_row + j] = store_tmp[ind]\n",
    "                ind += 1\n",
    "                tmp_row += 1\n",
    "        for i in range(1, row):\n",
    "            tmp_col = 0\n",
    "            store_tmp = []\n",
    "            while 0 < i + tmp_col  < row and 0 <= tmp_col < col:\n",
    "                store_tmp.append(mat[tmp_col + i][tmp_col])\n",
    "                tmp_col += 1\n",
    "            store_tmp = sorted(store_tmp)\n",
    "            print(store_tmp)\n",
    "            ind, tmp_col = 0, 0\n",
    "            while 0 <= i + tmp_col < row and 0 <= tmp_col < col:\n",
    "                mat[tmp_col + i][tmp_col] = store_tmp[ind]\n",
    "                ind += 1\n",
    "                tmp_col += 1\n",
    "        return mat\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        temp = []\n",
    "        for j in range(n):\n",
    "            x = 0\n",
    "            y = j\n",
    "            while x < m and y < n:\n",
    "                temp.append(mat[x][y])\n",
    "                x += 1\n",
    "                y += 1\n",
    "            x = 0\n",
    "            y = j\n",
    "            temp.sort(reverse=True)\n",
    "            while temp:\n",
    "                mat[x][y] = temp.pop()\n",
    "                x += 1\n",
    "                y += 1\n",
    "        for i in range(1, m):\n",
    "            x = i\n",
    "            y = 0\n",
    "            while x < m and y < n:\n",
    "                temp.append(mat[x][y])\n",
    "                x += 1\n",
    "                y += 1\n",
    "            x = i\n",
    "            y = 0\n",
    "            temp.sort(reverse=True)\n",
    "            while temp:\n",
    "                mat[x][y] = temp.pop()\n",
    "                x += 1\n",
    "                y += 1\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        before=[]\n",
    "        after=[]\n",
    "        print(mat)\n",
    "        if len(mat)==1 or len(mat[0])==1:\n",
    "            return mat\n",
    "        #左边\n",
    "        for i in range(len(mat)):\n",
    "            before=[]\n",
    "            for n in range(len(mat)-i):\n",
    "                before.append(mat[i+n][n])\n",
    "                if n==len(mat[0])-1 or i==len(mat)-1:\n",
    "                    break\n",
    "            before=sorted(before,reverse = True)\n",
    "            for n in range(len(mat)-i):\n",
    "                mat[i+n][n]=before.pop()\n",
    "                if n==len(mat[0])-1 or i==len(mat)-1:\n",
    "                    break\n",
    "        #右边\n",
    "        for i in range(1,len(mat[0])):\n",
    "            after=[]\n",
    "            for n in range(len(mat)):\n",
    "                after.append(mat[n][n+i])\n",
    "                if n+i==len(mat[0])-1 or n==len(mat)-1:\n",
    "                    break\n",
    "                \n",
    "            after=sorted(after,reverse=True)\n",
    "            for n in range(len(mat)):\n",
    "                mat[n][n+i]=after.pop()\n",
    "                if n+i==len(mat[0])-1 or n==len(mat)-1:\n",
    "                    break\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# trick: use `j - i` as the index for the data and simplify implementation.\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n, data = len(mat), len(mat[0]), defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                data[j - i].append(mat[i][j])\n",
    "        for l in data.values():\n",
    "            l.sort()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mat[i][j] = data[j - i][min(i, j)]\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: list[list[int]]) -> list[list[int]]:\n",
    "        sub = []\n",
    "        subs = []\n",
    "        rows = len(mat)\n",
    "        cols = len(mat[0])\n",
    "        res = [[0]*cols for i in range(rows)]\n",
    "        # res[0][1]=32\n",
    "        # print(res)\n",
    "        i,j = rows-1,0\n",
    "        while 0<=i<rows and 0<=j<cols:\n",
    "            i1, j1 = i, j\n",
    "            while i1>=0 and j1>=0:\n",
    "                sub.append(mat[i1][j1])\n",
    "                i1 -= 1\n",
    "                j1 -= 1\n",
    "            sub.sort()\n",
    "            i1 += 1\n",
    "            j1 += 1\n",
    "            for k in sub:\n",
    "                if(i1<rows and j1<cols):\n",
    "                    res[i1][j1] = k\n",
    "                    i1 += 1\n",
    "                    j1 += 1\n",
    "                else:\n",
    "                    pass\n",
    "\n",
    "            if(j<cols-1):\n",
    "                i = rows-1\n",
    "                j = j+1\n",
    "                sub = []\n",
    "            elif(i>0):\n",
    "                i = i-1\n",
    "                j = cols-1\n",
    "                sub = []\n",
    "            else:\n",
    "                break\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        d = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                d[i-j].append(mat[i][j])\n",
    "        for i in d.keys():\n",
    "            d[i].sort(reverse=True)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mat[i][j] = d[i-j].pop()\n",
    "        return mat\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        dic = collections.defaultdict(list)\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dic[i-j].append(mat[i][j])\n",
    "        for key in dic:\n",
    "            dic[key].sort(reverse = True)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mat[i][j] = dic[i - j].pop()\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        dic = collections.defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dic[i - j].append(mat[i][j])\n",
    "        for key in dic.keys():\n",
    "            dic[key].sort(reverse = True)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mat[i][j] = dic[i -j].pop()\n",
    "        return mat\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        #这个代码简直精妙\n",
    "        #首先，他发现横纵坐标之差相同的位置可以放在一起排序\n",
    "        #其次他找到了让数据重新变成矩阵的办法，从大到小排列，使用尾数据填充\n",
    "        #使用做好了矩阵，固定位置取用的方式，直接从字典中取到对应位置的数据\n",
    "        dic = collections.defaultdict(list)\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dic[i-j].append(mat[i][j])\n",
    "        for key in dic:\n",
    "            dic[key].sort(reverse = True)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mat[i][j] = dic[i - j].pop()\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0]) if len(mat) > 0 else 0\n",
    "        if m == 0 or n == 0:\n",
    "            return list()\n",
    "        \n",
    "        def get_sorted_line(x, y):\n",
    "            result = list()\n",
    "            while x < m and y < n:\n",
    "                result.append(mat[x][y])\n",
    "                x += 1\n",
    "                y += 1\n",
    "            result.sort()\n",
    "            return result\n",
    "        \n",
    "        def set_line(x, y, new_line):\n",
    "            i = 0\n",
    "            while x < m and y < n:\n",
    "                mat[x][y] = new_line[i]\n",
    "                x += 1\n",
    "                y += 1\n",
    "                i += 1\n",
    "        \n",
    "        for i in range(m-1, -1, -1):\n",
    "            line = get_sorted_line(i, 0)\n",
    "            set_line(i, 0, line)\n",
    "        for j in range(1, n):\n",
    "            line = get_sorted_line(0, j)\n",
    "            set_line(0, j, line)\n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        # 除了第一条和最后一条线，一共只有m + n - 3条线\n",
    "        for t in range(1, m + n - 2):\n",
    "            row = max(n - 1 - t, 0)\n",
    "            col = max(t - n + 1, 0)\n",
    "            l = []\n",
    "            while row < n and col < m:\n",
    "                # 利用堆排序\n",
    "                heappush(l, mat[row][col])\n",
    "                row += 1\n",
    "                col += 1\n",
    "\n",
    "            row = max(n - 1 - t, 0)\n",
    "            col = max(t - n + 1, 0)\n",
    "            while row < n and col < m:\n",
    "                mat[row][col] = heappop(l)\n",
    "                row += 1\n",
    "                col += 1\n",
    "        return mat\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        arr1 = [[] for _ in range(m)]\n",
    "        arr2 = [[] for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            t = i\n",
    "            l = 0\n",
    "            while(t!=m and l != n):\n",
    "                arr1[i].append(mat[l][t])\n",
    "                l += 1\n",
    "                t += 1\n",
    "        for i in range(n):\n",
    "            t = i\n",
    "            l = 0\n",
    "            while(t != n and l != m):\n",
    "                arr2[i].append(mat[t][l])\n",
    "                l += 1\n",
    "                t += 1\n",
    "        for key in arr1:\n",
    "            key.sort()\n",
    "        for key in arr2:\n",
    "            key.sort()\n",
    "        ans = [[0]* m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i > j:\n",
    "                    ans[i][j] = arr2[i-j][j]\n",
    "                else:\n",
    "                    ans[i][j] = arr1[j-i][i]\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
